package com.lizk.graph.prim;

import com.lizk.graph.weight.Edge;
import com.lizk.graph.weight.WeightGraph;
import com.lizk.heap.MinHeap;

import java.util.Arrays;

/**
 * @author lizhikui
 * @date 2020/2/23 13:01
 */
public class LazyPrim {
    public void lazyPrim(int n , WeightGraph<Edge<Integer>> graph){
       MinHeap<Edge<Integer>> minHeap = new MinHeap<>(100);

        boolean [] isV= new boolean[n];
        Arrays.fill(isV,false);

        int index = 0 ;
        while (true){
            if (!isV[index]){
                graph.iterator(index);
                while (graph.hasNext()){
                    minHeap.insertValue(graph.next());
                }
                isV[index] = true;
            }

            Edge<Integer> edge = null;
            while (true){
                edge = minHeap.takeValue();
                if (edge == null){
                    return;
                }
                if (edge.getFrom() == edge.getTo())
                    continue;
                if (isV[edge.getFrom()] && isV[edge.getTo()])
                    continue;
                index = isV[edge.getTo()]?edge.getFrom():edge.getTo();
                System.out.println(edge);
                break;
            }
        }




       /* for (int i = 0; i < n; i++) {
            graph.iterator(i);
            while (graph.hasNext()){
                minHeap.insertValue(graph.next());
            }

            Edge<Integer> edge = null;
            while (true){
                edge = minHeap.takeValue();
                if (edge == null){
                    break;
                }
                if(!isV[edge.getFrom()] || !isV[edge.getTo()]){
                    isV[edge.getFrom()] = true;
                    isV[edge.getTo()] = true;
                    System.out.println(edge);
                    break;
                }
            }
        }*/
    }
}
